/*	Program P12-4 Insert arc.

    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/

/*	====================== insertArc ====================== 
	Adds an arc vertex between two vertices.
	   Pre    fromKey is key of start vertex
	          toKey is key of destination vertex
	   Post   arc added to adjacency list
	   Return success  +1 if successful
	                   -1 if memory overflow
	                   -2 if fromKey not found
	                   -3 if toKey not found
*/

template <class TYPE, class KTYPE> 
int Graph<TYPE, KTYPE> :: insertArc (KTYPE fromKey, KTYPE toKey)
{
//	Local Definitions 
	Arc<TYPE>  *newPtr;
	Arc<TYPE>  *arcPredPtr;
	Arc<TYPE>  *arcWalkPtr;
	
	Vertex<TYPE>  *vertFromPtr;
	Vertex<TYPE>  *vertToPtr;

//	Statements 
	newPtr = new Arc<TYPE>;
	if (!newPtr)
	   return (-1);

	// Locate source vertex 
	vertFromPtr = first;
	while (vertFromPtr 
	       && fromKey > (vertFromPtr->data).key)
	    vertFromPtr = vertFromPtr->pNextVertex;
	if (!vertFromPtr || fromKey != (vertFromPtr->data).key)
	   return (-2);
	
	//  Now locate to vertex 
	vertToPtr   = first;
	while (vertToPtr 
	       && toKey > (vertToPtr->data.key))
	    vertToPtr   = vertToPtr->pNextVertex;
	if (!vertToPtr 
	     || toKey !=  (vertToPtr->data).key)
	   return (-3);
	   
	// From and to vertices located. Insert new arc. 
	++vertFromPtr->outDegree;
	++vertToPtr->inDegree;
	newPtr->destination = vertToPtr;
	if (!vertFromPtr->pArc)
	   {
	    // Inserting first arc for this vertex 
	    vertFromPtr->pArc = newPtr;
	    newPtr-> pNextArc = NULL;
	    return 1;
	   } // if new arc 
	
	// Find insertion point in adjacency (arc) list 
	arcPredPtr = NULL;
	arcWalkPtr = vertFromPtr->pArc;
	while (arcWalkPtr
	  && toKey >= (arcWalkPtr->destination->data.key))
	   {
	    arcPredPtr = arcWalkPtr;
	    arcWalkPtr = arcWalkPtr->pNextArc;
	   } // arcWalkPtr && 
	
	if (!arcPredPtr)
	    // Insertion before first arc 
	    vertFromPtr->pArc    = newPtr;
	else
	    arcPredPtr->pNextArc = newPtr;
	newPtr->pNextArc = arcWalkPtr;
  return 1;
}	// insertArc 
